package day20210712;

import treenode.SimpleTreeNode;

/**
 * 543. 二叉树的直径
 *
 * @author lizy
 * @date 2021/07/12
 */
public class Solution2 {

    public static void main(String[] args) {
        Solution2 solution = new Solution2();
        SimpleTreeNode simpleTreeNode = new SimpleTreeNode();
        simpleTreeNode.val = 6;
        simpleTreeNode.right = new SimpleTreeNode(8);
        simpleTreeNode.right.right = new SimpleTreeNode(9);
        simpleTreeNode.right.left = new SimpleTreeNode(7);
        simpleTreeNode.left = new SimpleTreeNode(2);
        simpleTreeNode.left.left = new SimpleTreeNode(1);
        System.out.println("=================================");
        System.out.println(solution.diameterOfBinaryTree(simpleTreeNode));
        System.out.println("=================================");
    }

    int ans;
    public int diameterOfBinaryTree(SimpleTreeNode root) {
        ans = 1;
        depth(root);
        return ans - 1;
    }
    public int depth(SimpleTreeNode node) {
        if (node == null) {
            // 访问到空节点了，返回0
            return 0;
        }
        // 左儿子为根的子树的深度
        int L = depth(node.left);
        // 右儿子为根的子树的深度
        int R = depth(node.right);
        // 计算d_node即L+R+1 并更新ans
        ans = Math.max(ans, L+R+1);
        // 返回该节点为根的子树的深度
        return Math.max(L, R) + 1;
    }
}
